Packet classification lists, of which Access Control Lists (ACLs) are a special case, consists of an ordered series of rules, where each rule has a match criterion and an action. An ACL is applied to a piece of data by evaluating the data against these rules in order and taking the action of the first rule that matched. For example, a match criterion for each rule is a pair (V, M), where V is a numeric value up to N bits long and M is a mask of N bits having a binary value of 0 or 1. A value X matches the rule if (X & M)=(V & M), where “&” is the bitwise “logical and” operator.
In one example, the values (X) matched against an ACL entry/rule are Internet Protocol (IP) v4 or IPv6 addresses. In this example, the (V, M) pairs match subsets of the IPv4 or IPv6 address space, and the actions of an ACL are either “permit” or “deny”. Also, each ACL is terminated by an “implicit deny” rule at the end equivalent to “deny (0, 0),” which denies every address that is not explicitly covered by another preceding rule in the ACL.
In addition, because the ACL is ordered, preceding rules in the ACL can overrule some or all of a subsequent rule for overlapping ranges of addresses. For example, if the ordered rules are “permit 128.1.1.0/24, permit 128.1.2.0/24, and deny 128.1.0.0/20,” because the permit rules are ordered higher in the ACL, the permit rules overrule the overlapping address ranges of the deny rule. As a result, the addresses are permitted by this ACL are “128.1.1.0-128.1.2.255” and the addresses denied are “128.1.0.0-128.1.0.255” and “128.1.3.0-128.1.255.255”. One problem with an ordered ACL is that the ACL can include hundreds or thousands of rules and evaluating this ACL can require complicated hardware resources of the network element, such as a ternary content addressable memory (TCAM) that is used to evaluate the ordered rules.